1. Field of the Invention
The invention relates generally to the field of arrangements in which data processing systems employing multiple special-purpose processors control or schedule the processing of tasks or processes, and more particularly to arrangements by which instructions for processing tasks or processes are transferred among the processors forming such a multi-processing system.
2. Description of the Prior Art
The reduction in cost and size of processors used in electronic data processing systems over the last few years has given rise to a dramatic increase in the number of processors, particularly microprocessors, that are used in data processing systems. Processors are used in data processing systems both as part of processor units for processing user programs and as part of control units that control many of the peripheral storage elements such as disk and tape drives and input/output elements such as printers, keyboards and visual display devices, scientific instruments, card readers and punches, communications lines and the like.
In many instances, it is desirable to use separate processor units in a system to execute various classes of instructions. For example, many systems have separate processor units constructed to execute floating point instructions or fixed point instructions or to perform matrix operations or operate on or search strings of characters. Special processor units are designed to speed execution of these instructions. Furthermore, in some instances the separate processor units may be able to execute instructions simultaneously, thereby speeding operation of the system.
The use of processors in peripheral and input/output control units allows a processor unit to use high-level commands to the control units that only generally defines the operations to be performed, and the control unit itself then determines the detailed operations that must be performed to carry out the operations required by the commands. Furthermore, processors in the control unit can initiate and perform diagnostics or maintenance on the attached peripheral units without intervention of the processing unit or units, thereby freeing them to concentrate on executing user programs. This arrangement substantially lessens the amount of direct attention that a processor unit must give to the detailed operations of the peripheral and input/output elements.
Systems employing multiple processors generally have one of two types of arrangements for controlling and scheduling the performance of tasks by the various processors, both of which are described in S. Madnick, et al., Operating Systems, (McGraw-Hill Book Company, New York, New York: 1974) at pages 244-247. In one arrangement, a master processor generates tasks required by a user program, for example, and distributes them to the slave processors. The master processor generally monitors the status of the slave processors. To initiate an operation by the slave processor, the master interrupts the slave, and when the slave processor finishes the task, it interrupts the master processor to indicate status. The master processor may then assign the slave a new task. The master processor may also perform diagnostic and maintenance programs on the system.
The use of a master processor simplifies scheduling, but if the demands on the master processor are heavy, it may become overloaded, thereby slowing down the system. Furthermore, the requirement that the master and slave processors communicate by interrupts further adds to the overhead, as time is required for both processors to service the interrupts.
The second arrangement eliminates the necessity of dedicating a processor solely to generating tasks and scheduling. In this arrangement, a state list of processes and their status are stored so as to allow any processor to have access to the list. Whenever a processor must stop execution of a process, it updates the process's status in the state list and then finds another process to run. In such a system employing decentralized control, it is necessary to establish good coordination and communication among all of the processors to ensure that a process is being processed by only one processor at a time, and also to ensure that all processes are processed. As the number of processors in the system increases, satisfactory communication and coordination becomes more difficult to achieve.